
//
// Created by Lenovo on 2020/10/3.
//

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
vector<ll>ans;
ll cnt;
int gcd(ll x,ll y)
{
    return y==0 ? x : gcd(y,x%y);
}
int check(ll x)
{
    int len = 0;
    while(x)
    {
        len++;
        x = x/10;
    }
    return len;
}
ll join(ll x,ll y)
{
    ll num[20];
    ll ans = x;
    int k = 0;
    while(y)
    {
        num[k++] = y%10;
        y = y/10;
    }
    for(int i = k-1;i>=0;i--)
    {
        ans = ans*10+num[i];
    }
    return ans;
}
void init()
{
    for(ll i = 1;i<=1e5;i++)
    {
        for(ll j = i+1;j<=1e5;j++)
        {
            if(gcd(i,j)!=1) continue;
            if(i*j>=1e5) break;
            for(ll k = 1;k<=1e5/j/i;k++)
            {
                ll x = k*i*i;
                ll y = k*i*j;
                ll z = k*j*j;
                int len =  check(x)+check(y)+check(z);
                if(len>15) break;
                ll tmp = join(join(x,y),z);
                ans.push_back(tmp);
                while(1)
                {
                    if(z%i!=0) break;
                    z = z*j/i;
                    //debug(z);
                    int _len = check(z);
                    if(len+_len>15) break;
                    else
                    {
                        len += _len;
                        tmp = join(tmp,z);
                        ans.push_back(tmp);
                    }
                }
            }
        }
    }
    sort(ans.begin(),ans.end());
    cnt = unique(ans.begin(),ans.end()) - ans.begin();
}
int main()
{
    init();
    int t;
    int kcase = 0;
    scanf("%d",&t);
    while(t--)
    {
        ll l,r;
        scanf("%lld %lld",&l,&r);
        ll ansl = upper_bound(ans.begin(),ans.end(),l-1)-ans.begin();
        ll ansr = upper_bound(ans.begin(),ans.end(),r)-ans.begin();
        printf("Case #%d: %lld\n",++kcase,ansr-ansl);
    }

}
